template<class T>
struct DescartesTree {

	std::vector<int> left, right, stk;

	DescartesTree() {}

	DescartesTree(const std::vector<T>& v) {
		work(v);
	}

	void work(const std::vector<T>& v) {
		int n = v.size();
		left.resize(n, n);
		right.resize(n, n);
		for(int i = 0; i < n; i++) {
			while(!stk.empty() && v[i] < v[stk.back()]) {
				right[stk.back()] = left[i];
				left[i] = stk.back();
				stk.pop_back();
			}
			stk.push_back(i);
		}
		while(stk.size() > 1) {
			int x = stk.back();
			stk.pop_back();
			right[stk.back()] = x;
		}
	}
};